//
//  NumTrees.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/15.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  96. 不同的二叉搜索树

import UIKit

/*
 
 96. 不同的二叉搜索树
 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

 示例:

 输入: 3
 输出: 5
 解释:
 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

    1         3     3      2      1
     \       /     /      / \      \
      3     2     1      1   3      2
     /     /       \                 \
    2     1         2                 3
 
 */

class NumTrees: NSObject {
    
    /*
     可用动态规划思想解题
     
     设G(n)表示1 ... n 为节点组成的二叉搜索树的总个数，
     我们取其中k(1 <= i <= n)，此时左边数列构建二叉树总个数就是G(i-1)，右边则是G(n-i)，
     则以k为节点的总个数就是 G(i-1)*G(n-i)
     
     边界情况：G(0) = 1   G(1) = 1
   
            i=1
    G(n)=   ∑   G(i−1)⋅G(n−i)
            n
     
     */

    func numTrees(_ n: Int) -> Int {
    
        if n == 0{
            return 1
        }
        if n == 1 || n == 2 {
            return n
        }
        
        var G = Array.init(repeating: 0, count: n+1)
        G[0] = 1
        G[1] = 1
        for i in 2 ... n {
            for j in 1 ... i{
                G[i] += G[j-1]*G[i-j]
            }
        }
        
        return G[n]
    }
    /*
        数学解法
        我们在上述解法中推导出的G(n)函数的值在数学上被称为卡塔兰数Cn。卡塔兰数更便于计算的定义如下：

        C0 = 1

                2(2n+1)
        Cn+1 = --------- Cn
                  n+2
     
     */
    func numTrees2(_ n: Int) -> Int {
        var C = 1
        for i in 0 ... n-1{
            C = C*2*(2*i+1)/(i+2)
        }
        return C
    }
    
    
    
    
    /*
     递归解法
     */
    
    var memoryDic:[Int:Int] = [:]
    
    func numTrees3(_ n: Int) -> Int {
        if n == 0{
            return 1
        }
        if n == 1 || n == 2 {
            return n
        }
        
        if memoryDic[n] != nil {
            return memoryDic[n]!
        }
        
        var num = 0
        for i in 0 ..< n{
            //num += self.numTrees3(i-1) * self.numTrees3(n-i)
            num += self.numTrees3(i) * self.numTrees3(n-i-1)
        }
        
        memoryDic[n] = num
        return num
    }
}
